class Node{
    //每一个节点的结构
    constructor(value) {
        this.value = value //数据域
        this.next = undefined //指针域
    }
}

class LinkedList{
    constructor() {
        this.count = 0 //计数器
        this.head = undefined //链头，起始节点
    }

    push(value){ //在尾部新增一个值
        let node = new Node(value) //实例生成节点对象
        let current //当前遍历的节点
        if(!this.head){
            this.head = node
            //如果说当前链表里是空的，就说明head也是空的，那就直接把新增的设置为链表的第一个
        }else{ //如果链表第一个不为空，那我们就往后面数
            current = this.head //链表头为当前已经遍历的节点
            while(current.next){ //如果当前节点的指针域所指向的地方不为空的时候，说明它还不是最后一个节点，就继续循环遍历
                current = current.next //只要不是最后一个节点，就一直把当前所遍历到的那个节点的指向，指向下一个
            }
            current.next = node //如果遍历到了最后一个节点，跳出了循环，那么就把当前的指针域指向这被遍历到的最后一个节点
        }
        this.count++ //当在尾部添加完一个新值之后，计数器加一
    }

    removeAt(index){ //删除链表上面的第几个数据
        if(index >= 0 && index < this.count){ //如果要删除一个指定的数据，必须满足下标大于等于0且小于链表长度这两个条件
            let current = this.head
            let beRemoved //被删除的
            if(index = 0){ //如果删除的是第0个，链头
                beRemoved = current
                this.head = current.next //链头指向下一个数据，那么原来的链头数据就被删除了
            }else{ //这一步循环非常难理解，可以试着代入具体的数值0 1 2 3 4来理解
                for(let i = 1; i < index; i++){ //为啥从1开始，因为刚刚已经排除了第0位
                    current = current.next //当循环结束时，要被删除节点的前一个节点，i-1
                }
                beRemoved = current.next //待删除的节点，i，（current.next）.next
                current.next = current.next.next //当前节点的前一个节点的指针域 指向 当前节点的下一个节点，那么当前节点就被删除了
            }
            this.count--
            return beRemoved
        }
    }

    removeValue(value){
        let current = this.head
        let pre = null //被删除节点的前一个节点
        if(current.value === value){ //如果输入的值与链头的值相等
            this.head = current.next
        }else{
            for(let i =1; i < this.count; i++){
                pre = current //将i-1保存到变量pre
                current = current.next //需要被删除的节点i
                if(current.value === value){
                    pre.next = current.next //前一个节点（i-1）的指针域 指向 需要被删除的节点（i）的指针域所指向的节点（i+1）
                    break //删除符合条件的第一个值，如果没写break就是继续循环，删除符合条件的所有值
                }
            }
        }
        this.count--
    }

    pop(){ //模拟pop功能，删除最后一个
        return this.removeAt(this.count - 1)
    }

    indexOf(value){ //查询一个值在链表里面的位置，返回该值的位置下标
        let current = this.head
        if(value === current.value){ //三个等号全等，数据类型也要相同
            return 0
        }

        //如果不是第0位，那么就进入下面这个循环
        for(let i = 1; i < this.count; i++){
            current = current.next //不是第0位，那么就一直循环往后挪
            if(value === current.value){
                return i
            }
        }
        return undefined //如果既不是if里面的，也不是for循环里面的，那就说明找不到，找不到就返回undefined
    }

    getNodeAt(index){ //获取指定位置的值
        if(index >=0 && index < this.count){
            let current = this.head
            if(index === 0){
                return current
            }else{
                for(let i =1; i < index; i++){
                    current = current.next //当循环结束时，被剔除的节点的前一个节点
                }
                return current.next
            }
        }
    }

    insert(value,index){ //指定位置插入新节点
        let node = new Node(value)
        if(index >= 0 && index <= this.count){ //输入的索引值在链表长度内
            let current = this.head //先把原来开头的值保存下来
            if(index === 0){ //插入开头
                this.head = node
                this.head.next = current //把新的开头值的指针域 指向 原先开头的值
            }else{
                for(let i = 1; i < index; i++){
                    current = current.next //当循环结束时，插入新节点的位置 的 前一个节点 等号左边的current变量是i-1
                }
                let nextEle = current.next //nextEle保存原来的i
                current.next = node //i-1的指针域指向新插入的节点
                node.next = nextEle //新插入的节点的指针域指向原来的i
                this.count++
            }
        }else{ //输入的索引值超出链表长度
            throw new Error("索引值错误")
        }
    }

    isEmpty(){
        return !this.count
    }

    size(){
        return this.count
    }

    getHead(){
        return this.head.value
    }

    toString(){
        let objString = ""
        let current = this.head
        if(!current){ //如果链表头不存在
            return "" //返回空
        }else{
            do{ //至少会先执行一次do里面的循环
                objString = `${objString},${current.value}`
                current = current.next
            }while(current) //只要还有当前值，就一直进行do里面的循环
            return objString.slice(1)
        }
    }
}

class ValuePair{ //存储原始值
    constructor(key,value) { //单个的字典值的节点
        this.key = key
        this.value = value
    }
    toString(){
        return `[${this.key}:${this.value}]` //单个值节点转成字符串
    }
}

class HashTable{
    constructor(){
        this.table = {}
    }

    toStringFN(item){ //形参item就等同于key意思
        if(item === null){ //如果传入的key是null
            return ""
        }else if(item === undefined){ //如果传入的是undefined
            return "Undefined"
        }else if(typeof item === "string" || item instanceof String){ //如果传入的是与字符串有关的
            return `${item}`
        }
        //当然这个方法不算完美，因为有些对象名可能天生带有_id，所以可以生成一个非常复杂的独一无二的id识别码来避免这种情况
        if(item["_id"]){ //判断是否是被我们改造过的重名对象，这行代码替换掉了下面的set中注释掉的更新tablekey
            return item.toString() + item["_id"]
        }
        //如果以上情况都不是
        return item.toString()
    }

    loseloseHASHCode(key){ //将key转换成string，但是这样也依旧会算出相同的数，所以还需要再借助分离链接法
        if(typeof key === "number"){
            return key
        }
        let tablekey = this.toStringFN(key)
        let hashCode = 0
        //hash算法非常多，这里用一种遍历其中每一个字符，然后累加每一个字符的字符编码charCodeAt
        for(let i = 0; i < tablekey.length; i++){
            hashCode += tablekey.charCodeAt(i)
        }
        return hashCode % 37 //质数求余，除以任意一个质数取余，将取得的余数作为key，
        //密码学中非常难生成所有质数，因为质数无法用通项公式生成，所以用质数比较难被破解
    }

    add(key,value){ //散列表增加值
        if(key != null && key != undefined){
            let position = this.loseloseHASHCode(key) //将哈希函数生成的索引赋值给下标position
            if(!this.table[position]){ //如果该索引上不存在值，则添加一个散列表节点
                this.table[position] = new LinkedList() //分离链接法的散列表中每一个节点都是一个链表结构
            }
            //下面就是如果存在的情况
            this.table[position].push(new ValuePair(key,value)) //在该散列表节点索引的值上push进next指针域所指向的值
            return true //添加成功
        }
        return false //添加失败
    }

    get(key){ //通过索引key获取对应值
        let position = this.loseloseHASHCode(key)
        let linkdata = this.table[position]
        if(linkdata){ //当散列表中存在值
            let current = linkdata.head
            do{
                if(current.value.key === key){
                    return current.value
                }
                current = current.next
            }while(current)
        }
    }

    remove(key){ //通过索引key删除对应值
        let position = this.loseloseHASHCode(key)
        let linkdata = this.table[position]
        if(linkdata){ //当散列表中存在值
            let current = linkdata.head
            do{
                if(current.value.key === key){
                    linkdata.removeValue(current.value)
                }
                current = current.next
            }while(current)
        }
    }
}

let h = new HashTable()
h.add("hello",1)
h.add("world",2)
h.get("world")
h.remove("hello")